/*
 * @lc app=leetcode id=96 lang=cpp
 *
 * [96] Unique Binary Search Trees
 */
class Solution {
private:
    unordered_map<uint64_t, int> rec;
public:
    int numTrees(int n) {
        if (n <= 1) {
            return n;
        }
        
        return generateTrees(1, n);
    }

    int generateTrees(int m, int n) {

        if (m >= n) {
            return 1;
        }

        uint64_t key = m;
        key = key << 32 | n;
        if (rec[key] > 0) {
            return rec[key];
        }
        int sum = 0;
        for (int i=m; i<=n; i++) {
            sum += generateTrees(m, i-1) * generateTrees(i+1, n);
        }
        rec[key] = sum;
        return sum;
    }
};

